/**
 * 
 */
package algoritmos;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

import modelo.Aresta;
import modelo.Grafo;
import modelo.Vertice;

/**
 * M�todo de Kruskal
 * 
 * TODO: Terminar o m�todo, ainda est� com problemas
 * 
 * @author Rogerio
 *
 */
public class Kruskal {
	
	public static boolean kruskal(Grafo grafo){
		ArrayList<Aresta> listaDeArestas = new ArrayList<Aresta>(grafo.getArestas());
		/**
		 * Ordenando
		 */
		Collections.sort(listaDeArestas, new Comparator<Aresta>() {
			@Override
			public int compare(Aresta o1, Aresta o2) {
				if(o1.getPeso() > o2.getPeso()){
					return 1;
				}else if (o1.getPeso() < o2.getPeso()){
					return -1;
				}else{
					return 0;
				}
			}
		});
		/**
		 * Fim ordena��o
		 */
		
		//Criando o conjunto de grupos (�rvore)
		//Cada �rvore recebe um n�mero de grupo diferente
		HashMap<Vertice,Integer> conjFinalVertices = new HashMap<Vertice, Integer>();
		int grupo = 0;
		for(Vertice v : grafo.getVertices()){
			conjFinalVertices.put(v, grupo);
			grupo++;
		}
		
		List<Aresta> conjFinalArestas = new ArrayList<Aresta>();
		
		int i = 0;
		//n�mero de arestas escolhidas = (n-1)
		while((grafo.getVertices().size() - 1) != conjFinalArestas.size()){
			if(listaDeArestas.size() > 0){ //Grafo vazio
				if(i < listaDeArestas.size()){ //todas as arestas foram analisadas
					if(conjFinalArestas.isEmpty()){//primeira aresta a ser adicionada
						Aresta exam = listaDeArestas.get(i);
						conjFinalArestas.add(exam);
						//modifico o grupo do v�rtice destino da aresta
						conjFinalVertices.put(exam.getDestino(),conjFinalVertices.get(exam.getOrigem()));
						i++;
					}else{
						
						Aresta exam = listaDeArestas.get(i);
						
						//Compara��o para verificar se est�o no mesmo grupo
						if(conjFinalVertices.get(exam.getOrigem()) == conjFinalVertices.get(exam.getDestino())){
							i++;
						}else{
							conjFinalArestas.add(exam);
							
							//Pego o grupo do v�rtice de origem e de destino
							int grupoOrigem = conjFinalVertices.get(exam.getOrigem());
							int grupoDestino = conjFinalVertices.get(exam.getDestino());
							
							//Modifico o grupo de todos os v�rtices que pertencem ao grupo de destino
							for(Vertice vertice : conjFinalVertices.keySet()){
								if(conjFinalVertices.get(vertice) == grupoDestino){
									conjFinalVertices.put(vertice, grupoOrigem);
								}
							}
							i++;
						}
					}
				}else{
					System.out.println("Problemas - Provavelmente grafo desconectado - Gerar novo grafo");
					return false;
				}
			}else{
				System.out.println("Nenhuma aresta para adicionar");
				return false;
			}
		}
		return true;
		//System.out.println(conjFinalVertices);
	}
}
